#include <iostream>
#include <stack>

using namespace std;
// 1249. 移除无效的括号
// 给你一个由 '('、')' 和小写字母组成的字符串 s。
// 你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> st;

        for(int i = 0; i < s.size(); i++)
        {
            char ch = s.at(i);
            if(ch == '(')
                st.push(i);
            else if(ch == ')')
            {
                if(!st.empty() && s[st.top()] == '(')
                    st.pop();
                else
                    st.push(i);
            }
        }
        // 从s中删除无效的括号
        while(!st.empty())
        {
            int i = st.top();
            st.pop();
            s.erase(s.begin() + i); // 通过覆盖的方式删除相应的字符
        }
        return s;
    }
};
int main() {
    std::cout <<boolalpha<<Solution().minRemoveToMakeValid("lee(t(c)o)de)") << std::endl;
    // "lee(t(co)de)" , "lee(t(c)ode)"
    std::cout <<boolalpha<<Solution().minRemoveToMakeValid("a)b(c)d") << std::endl;
    // "ab(c)d"
    std::cout <<boolalpha<<Solution().minRemoveToMakeValid("))((") << std::endl;
    return 0;
}
